package me.timlong;

public class RopeCutting {
    /**
     * 题目描述
     * 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），
     * 每段绳子的长度记为k[0],k[1],...,k[m]。
     * 请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？
     * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，
     * 此时得到的最大乘积是18。
     */
    public int cutRope(int target) {

        if(target == 2)
            return 1;
        else if(target == 3)
            return 2;
        int[] dp = new int[target + 1];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        int res = 0;

        for(int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++)
                res = Math.max(res, dp[j] * dp[i - j]);
            dp[i] = res;
        }

        return dp[target];
    }

    /**
     * 分析：由于m， target > 1,说明绳子至少必须cut一次
     * 对于
     * target = 2， max = 1 < target
     * target = 3， max = 2 < target
     * target = 4， max = 2 * 2 = 4 >= target
     * target = 5， max = 2 * 3 = 6 >= target
     * 。。。
     * 考虑到 target < 3时， max multiple value < target
     * 而一旦target > 3时，则必须考虑截断绳子，因为截断比不截断绳子获得更大的max value
     * 此时动态规划中从底向上推导的最简单情形为pro[0] = 0, pro[1] = 1, pro[2] = 2, pro[3] = 3,
     * 从target = 4开始进行遍历，基于最简单的情形进行计算
     *
     * 因此这三种情况单独考虑
     *
     * @param target
     * @return
     */
    public int ropeCut(int target){
        if(target < 2)
            return 0;
        else if(target == 2)
            return 1;
        else if(target == 3)
            return 2;

        int[] pro = new int[target + 1];
        pro[0] = 0;
        pro[1] = 1;
        pro[2] = 2;
        pro[3] = 3;

        int max = 0; // i增加，max总会扩大，一次第一层循环内不需要max归零
        int tmp;
        for (int i = 4; i <= target ; i++) {
            for (int j = 1; j <= i / 2 ; j++) {
                   tmp = pro[j] * pro[i - j];
                   max = max < tmp ? tmp : max;
            }
            pro[i] = max;
        }

        return pro[target];
    }


    /**
     *  此题貌似greedy算法更简单，因为只要是大于3的绳子长度就应该被截断为
     *  2， 3的片段组成，截断为3的越多，乘积的值越大，所谓greedy strategy.
     *  关键是考虑最后的情况，最后剩下4时，应该取2 * 2可以获得最大值。
     * @param target
     * @return
     */
    public int greedyRopeCut(int target){
        int threeLen = target / 3;
        int leftLen = target % 3;

        // 余数的情况分为三种0， 1， 2
        if(0 == leftLen)
            return (int)Math.pow(3, threeLen);
        else if(2 == leftLen)
            return (int)Math.pow(3, threeLen) * 2;
        else
            return (int)Math.pow(3, threeLen - 1) * 2;
    }



    public static void main(String[] args) {
        System.out.println("Dynamic result ==> " + new RopeCutting().ropeCut(100));
        System.out.println("Greedy result ==> " + new RopeCutting().ropeCut(100));
    }


}
